package warm100;

import java.util.ArrayList;
import java.util.List;

public class orangesRotting_994 {
    public static final int [][] direction={
            {0,1},   //向右
            {0,-1}, //向左
            {1,0},   // 向下
            {-1,0}}; //向上
    public int orangesRotting(int[][] grid) {
        //能想到的记忆化搜索，或者计算最长路径复杂度都太高了
        //试试计算每个新鲜橘子距离腐败橘子的最长路径
        //同时维护一个最长路径
        int m = grid.length, n = grid[0].length;
        List<int[]>bad=new ArrayList<>();  //坏橘子个数
        int fresh=0,time=0;   //新鲜橘子个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1)
                    fresh++;
                if (grid[i][j] == 2)
                    bad.add(new int[]{i,j});  //加入坐标
            }
        }
        while( fresh != 0  && !bad.isEmpty()){    //新鲜橘子数量降为0，全部腐烂完
            time++;   //时间增加
            List<int[]>tmp=bad;  //存储上一轮的感染的橘子
            bad=new ArrayList<>();   //存储这一轮感染的橘子
            for (int[] index:tmp){  //每个坏橘子感染其四个方向的橘子
                for(int [] dir:direction){
                    int i=index[0]+dir[0];     //行坐标变化
                    int j=index[1]+dir[1];     //列坐标变化
                    if(i!=-1 && i!=m && j!=-1 && j!=n &&grid[i][j]==1){
                            fresh--;
                            grid[i][j]=2;
                            bad.add(new int[]{i,j});
                    }
                }
            }
        }
        if(fresh!=0) return -1;
        else return time;
    }
}
